package GraphType.digitalPyramid;

import java.util.*;

import static GraphType.shortestPath.DFS.printMatrix;
/*
3
1
2
3
4
5
6
* */
public class DFS {
    static int[][] a = new int[10][10];
    static int ans;
    static int n;
    static Stack<Integer> path = new Stack<>();

    public static void main(String[] args) {
        init();
        path.add(a[1][1]);
        dfs(1,1,a[1][1]);
        System.out.println(ans);

    }
    static void init(){
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <= i; j++) {
                a[i][j]=scanner.nextInt();
            }
        }
        printMatrix(a);
        ans = 0;
    }
    static void dfs(int x, int y, int cur) {
        if (x == n) {//到达底部
            System.out.println(path);
            if (cur > ans) ans = cur;
            return;
        }
        //点(x,y)可以向左下和右下两个方向走
        path.push(a[x + 1][y]);
        dfs(x + 1, y, cur + a[x + 1][y]);
        path.pop();
        path.push(a[x + 1][y + 1]);
        dfs(x + 1, y + 1, cur + a[x + 1][y + 1]);
        path.pop();
//        if (v[x + 1][y] == 0) { 因为只有两个方向不可逆，所以不用判断是否访问过
//            path.push(a[x + 1][y]);
//            v[x + 1][y] = 1;
//            dfs(x + 1, y, cur + a[x + 1][y]);
//            v[x + 1][y] = 0;
//            path.pop();
//        }
//        if (v[x + 1][y + 1] == 0) {
//            path.push(a[x + 1][y + 1]);
//            v[x + 1][y + 1] = 1;
//            dfs(x + 1, y + 1, cur + a[x + 1][y + 1]);
//            v[x + 1][y + 1] = 0;
//            path.pop();
//        }
    }
}
